
//leetcode submit region begin(Prohibit modification and deletion)
package leetcode.editor.cn;

import java.util.ArrayDeque;

/**
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * 示例 1：
 *
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 *
 * 输入：s = "(]"
 * 输出：false
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 仅由括号 '()[]{}' 组成
 *
 */

/**
 * 如果是左，就放入左栈；如果是右，则对比栈顶，是他的左，就pop,否则返回失败
 */
class Solution20 {
    public boolean isValid(String s) {

        ArrayDeque<Character> left = new ArrayDeque<>();
        for(char c : s.toCharArray()){

            if (c == '{' || c == '(' ||c == '['){
                left.push(c);
            }else {
                // 是右符号
                if (!left.isEmpty() && leftChar(c) == left.getFirst()){
                    left.pop();
                }else {
                    // 和最近的左括号不匹配
                    return false;
                }
            }
        }
        // 是否所有的左括号都被匹配了
        return left.isEmpty();
    }

    /**
     * 返回右括号对应的 左括号
     */

    public char leftChar(char c){

        if (c == '}'){
            return '{';
        }
        if (c == ')'){
            return '(';
        }

        return '[';


    }






}

